{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Max Sum of Rectangle No Larger Than K"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #matrix #ordered-set #prefix-sum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #矩阵 #有序集合 #前缀和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxSumSubmatrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #矩形区域不超过 K 的最大数值和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个 <code>m x n</code> 的矩阵 <code>matrix</code> 和一个整数 <code>k</code> ，找出并返回矩阵内部矩形区域的不超过 <code>k</code> 的最大数值和。</p>\n",
    "\n",
    "<p>题目数据保证总会存在一个数值和不超过 <code>k</code> 的矩形区域。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/03/18/sum-grid.jpg\" style=\"width: 255px; height: 176px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[1,0,1],[0,-2,3]], k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>蓝色边框圈出来的矩形区域 <code>[[0, 1], [-2, 3]]</code> 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>matrix = [[2,2,-1]], k = 3\n",
    "<strong>输出：</strong>3\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == matrix.length</code></li>\n",
    "\t<li><code>n == matrix[i].length</code></li>\n",
    "\t<li><code>1 <= m, n <= 100</code></li>\n",
    "\t<li><code>-100 <= matrix[i][j] <= 100</code></li>\n",
    "\t<li><code>-10<sup>5</sup> <= k <= 10<sup>5</sup></code></li>\n",
    "</ul>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>进阶：</strong>如果行数远大于列数，该如何设计解决方案？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [max-sum-of-rectangle-no-larger-than-k](https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [max-sum-of-rectangle-no-larger-than-k](https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,0,1],[0,-2,3]]\\n2', '[[2,2,-1]]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        row , col = len(matrix) , len(matrix[0])\n",
    "        res = float(\"-inf\")\n",
    "        for left in range(col):\n",
    "            sums = [0] * row\n",
    "            for right in range(left,col):\n",
    "                for j in range(row):\n",
    "                    sums[j] += matrix[j][right]\n",
    "                lst = [0]\n",
    "                cur = 0\n",
    "                for num in sums:\n",
    "                    cur += num\n",
    "                    loc = bisect.bisect_left(lst,cur-k)\n",
    "                    if loc < len(lst):\n",
    "                        res = max(cur-lst[loc],res)\n",
    "                    bisect.insort(lst,cur)\n",
    "        return res\n",
    "\n",
    "# 作者：小周小周万事无忧\n",
    "# 链接：https://leetcode.cn/problems/max-sum-of-rectangle-no-larger-than-k/solutions/402080/ju-xing-qu-yu-bu-chao-guo-kde-zui-da-shu-zhi-he-py/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from sortedcontainers import SortedList\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        dp = [[0]*(n) for _ in range(m)]\n",
    "\n",
    "        ans = 0\n",
    "        dp[0][0] = matrix[0][0]\n",
    "        for i in range(1, m):\n",
    "            dp[i][0] = dp[i-1][0]+matrix[i][0]\n",
    "        for j in range(1, n):\n",
    "            dp[0][j] = dp[0][j-1]+matrix[0][j]\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                dp[i][j] = dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+matrix[i][j]\n",
    "\n",
    "        ans = float('-inf')\n",
    "        for p in range(m):\n",
    "            for i in range(p, m):\n",
    "                pre = SortedList()\n",
    "                pre.add(0)\n",
    "                for j in range(n):\n",
    "                    if p >= 1:\n",
    "                        ind = bisect.bisect_left(pre, dp[i][j]-dp[p-1][j]-k)\n",
    "                        if ind < len(pre):\n",
    "                            ans = max(ans, dp[i][j]-dp[p-1][j]-pre[ind])\n",
    "                        pre.add(dp[i][j]-dp[p-1][j])\n",
    "                    else:\n",
    "                        ind = bisect.bisect_left(pre, dp[i][j] - k)\n",
    "                        if ind < len(pre):\n",
    "                            ans = max(ans, dp[i][j] - pre[ind])\n",
    "                        pre.add(dp[i][j])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\r\n",
    "from sortedcontainers import sortedlist\r\n",
    "from sortedcontainers.sortedset import SortedSet\r\n",
    "\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def maxSumSubmatrix(self, m: List[List[int]], tar: int) -> int:\r\n",
    "        mm=len(m)+1\r\n",
    "        nn=len(m[0])+1\r\n",
    "        s=[[0]*nn for _ in range(mm)]\r\n",
    "        from sortedcontainers import SortedList\r\n",
    "\r\n",
    "        for i in range(1,mm):\r\n",
    "            for j in range(1,nn):\r\n",
    "                s[i][j]=-s[i-1][j-1]+s[i][j-1]+s[i-1][j]+m[i-1][j-1]\r\n",
    "        res=float('-inf')\r\n",
    "        print(s)\r\n",
    "        for i in range(nn):\r\n",
    "            for j in range(i):\r\n",
    "                \r\n",
    "                sett=SortedList()\r\n",
    "                for k in range(0,mm):\r\n",
    "                    ts=s[k][i]-s[k][j]\r\n",
    "                    print(ts)\r\n",
    "                    idx=sett.bisect_left(ts-tar)\r\n",
    "                    if idx<len(sett):\r\n",
    "                        res=max(res,ts-sett[idx])\r\n",
    "                    sett.add(ts)\r\n",
    "        return res\r\n",
    "s=Solution()\r\n",
    "lst=[[2,2,-1]]\r\n",
    "print(s.maxSumSubmatrix(lst,0))\r\n",
    "                    \r\n",
    "\r\n",
    "\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m=len(matrix)\n",
    "        n=len(matrix[0])\n",
    "        ans=float('-inf')\n",
    "\n",
    "        for i in range(m):\n",
    "            pre=[0]*n\n",
    "            for j in range(i,m):\n",
    "                for _ in range(n):\n",
    "                    pre[_]=pre[_]+matrix[j][_]\n",
    "                s=0\n",
    "                sortset=[0]\n",
    "                for v in pre:\n",
    "                    s=s+v\n",
    "                    idx=bisect_left(sortset,s-k)\n",
    "                    if idx!=len(sortset):\n",
    "                        ans=max(ans,s-sortset[idx])\n",
    "                    bisect.insort(sortset,s)\n",
    "                    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = float('-inf')\n",
    "\n",
    "        for i in range(m):\n",
    "            # 初始化每一列的前缀和为 0\n",
    "            sums = [0] * n\n",
    "\n",
    "            for j in range(i, m):\n",
    "                # 更新每一列的前缀和\n",
    "                for c in range(n):\n",
    "                    sums[c] += matrix[j][c]\n",
    "\n",
    "                sorted_sums = [0] # 初始化有序集合\n",
    "                cur_sum = 0 # 初始化前缀和\n",
    "                for s in sums:\n",
    "                    cur_sum += s # 计算当前前缀和\n",
    "                    idx = bisect_left(sorted_sums, cur_sum - k) # 查找符合要求的前缀和\n",
    "                    if idx < len(sorted_sums):\n",
    "                        # 如果存在符合要求的前缀和，则计算当前子矩阵的元素和\n",
    "                        res = max(res, cur_sum - sorted_sums[idx])\n",
    "                    bisect.insort(sorted_sums, cur_sum) # 将当前前缀和插入有序集合中\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = float('-inf')\n",
    "        # 枚举子矩阵的上下边界\n",
    "        for i in range(m):\n",
    "            # 初始化每一列的前缀和为 0\n",
    "            sums = [0] * n\n",
    "            for j in range(i, m):\n",
    "                # 更新每一列的前缀和\n",
    "                for c in range(n):\n",
    "                    sums[c] += matrix[j][c]\n",
    "                # 利用有序集合进行优化\n",
    "                # 类似两数之和的思路，求前缀和的最大值和最小值之差等于 k\n",
    "                # 利用有序集合维护前缀和的有序性\n",
    "                # 利用双指针查找符合要求的前缀和\n",
    "                sorted_sums = [0] # 初始化有序集合\n",
    "                cur_sum = 0 # 初始化前缀和\n",
    "                for s in sums:\n",
    "                    cur_sum += s # 计算当前前缀和\n",
    "                    idx = bisect_left(sorted_sums, cur_sum - k) # 查找符合要求的前缀和\n",
    "                    if idx < len(sorted_sums):\n",
    "                        # 如果存在符合要求的前缀和，则计算当前子矩阵的元素和\n",
    "                        res = max(res, cur_sum - sorted_sums[idx])\n",
    "                    bisect.insort(sorted_sums, cur_sum) # 将当前前缀和插入有序集合中\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = float(\"-inf\")\n",
    "        #i, j是子矩阵的上边界和下边界\n",
    "        for i in range(m):\n",
    "            #需要重新构建列的数值和\n",
    "            Sum = [0] * n\n",
    "            for j in range(i, m):\n",
    "                sort_list = [0]\n",
    "                pre_sum = 0\n",
    "                for p in range(n):\n",
    "                    Sum[p] += matrix[j][p]\n",
    "                    pre_sum += Sum[p]\n",
    "                    idx = bisect.bisect_left(sort_list, pre_sum-k)\n",
    "                    if idx < len(sort_list):\n",
    "                        res = max(res, pre_sum-sort_list[idx])\n",
    "                    bisect.insort(sort_list, pre_sum)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m): #枚举上边界\n",
    "            total = [0] * n\n",
    "            for j in range(i, m): \n",
    "                # 按行更新 前缀和\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c] #区间 [l,r)的区间和\n",
    "                \n",
    "                totalSet = [0]\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v #在枚举s的同时维护一个存储Si(i<r)的有序集合\n",
    "                    \n",
    "                    #约束 Sr−Sl≤k 可以转换为 Sl ≥ Sr−k\n",
    "                    lb = bisect_left(totalSet,s - k)\n",
    "                    if lb < len(totalSet):\n",
    "                        ans = max(ans, s - totalSet[lb])\n",
    "                    \n",
    "                    totalSet.append(s)\n",
    "                    totalSet.sort()\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        res = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            dp = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for col in range(n):\n",
    "                    dp[col] += matrix[j][col]\n",
    "                num = 0\n",
    "                tmp = [0]\n",
    "                for ind, val in enumerate(dp):\n",
    "                    num += val\n",
    "                    left, right = 0, ind\n",
    "                    while left <= right:\n",
    "                        mid = left + (right - left) // 2\n",
    "                        if tmp[mid] < num - k:\n",
    "                            left = mid + 1\n",
    "                        else:\n",
    "                            right = mid - 1\n",
    "                    if left <= ind:\n",
    "                        res = max(res, num - tmp[left])\n",
    "                    left, right = 0, ind\n",
    "                    while left <= right:\n",
    "                        mid = left + (right - left) // 2\n",
    "                        if tmp[mid] < num:\n",
    "                            left = mid + 1\n",
    "                        else:\n",
    "                            right = mid - 1\n",
    "                    tmp.insert(left, num)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = -200000\n",
    "        for i in range(m):\n",
    "            sum1 = [0] * n\n",
    "            for j in range(i, m, 1):\n",
    "                for c in range(n):\n",
    "                    sum1[c] += matrix[j][c]\n",
    "                sumSet = {0}\n",
    "                s = 0\n",
    "                ST = [0] * (n + 1)\n",
    "                for d in range(n):\n",
    "                    s += sum1[d]\n",
    "                    ST[d + 1] = s\n",
    "                for p in range(n):\n",
    "                    for q in range(p + 1, n + 1, 1):\n",
    "                        cc = ST[q] - ST[p]\n",
    "                        if cc <= k and cc > res:\n",
    "                            res = cc\n",
    "                       \n",
    "        return res\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -2147483247\n",
    "\n",
    "        for i in range(m):\n",
    "            cols = [0 for _ in range(n)]\n",
    "            for low in range(i, m):\n",
    "                for j in range(n):\n",
    "                    cols[j] += matrix[low][j]\n",
    "\n",
    "                area = [0]\n",
    "                val = 0\n",
    "                for col in cols:\n",
    "                    val += col\n",
    "                    lb = bisect.bisect_left(area, val - k)\n",
    "                    if lb != len(area):\n",
    "                        ans = max(ans, val - area[lb])\n",
    "\n",
    "                    area.append(val)\n",
    "                    area.sort()\n",
    "\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        import math\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -math.inf\n",
    "        for i in range(m):\n",
    "            prefix_sum = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for l in range(n):\n",
    "                    prefix_sum[l] += matrix[j][l]\n",
    "                for left in range(n):\n",
    "                    sums = 0\n",
    "                    for right in range(left, n):\n",
    "                        sums += prefix_sum[right]\n",
    "                        if sums == k:\n",
    "                            return k\n",
    "                        elif k> sums > ans:\n",
    "                            ans = sums\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        row , col = len(matrix) , len(matrix[0])\n",
    "        res = float(\"-inf\")\n",
    "        for left in range(col):\n",
    "            sums = [0] * row\n",
    "            for right in range(left,col):\n",
    "                for j in range(row):\n",
    "                    sums[j] += matrix[j][right]\n",
    "                lst = [0]\n",
    "                cur = 0\n",
    "                for num in sums:\n",
    "                    cur += num\n",
    "                    loc = bisect.bisect_left(lst,cur-k)\n",
    "                    if loc < len(lst):\n",
    "                        res = max(cur-lst[loc],res)\n",
    "                    bisect.insort(lst,cur)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "        res = -inf\n",
    "        for i in range(m):\n",
    "            sums = [0]*n\n",
    "            for j in range(i,m):\n",
    "                for c in range(n):\n",
    "                    sums[c]+=matrix[j][c]\n",
    "                \n",
    "                sorted_num = [0]\n",
    "                cum_sum = 0\n",
    "                for s in sums:\n",
    "                    cum_sum+=s\n",
    "                    idx = bisect.bisect_left(sorted_num,cum_sum-k)\n",
    "                    if idx<len(sorted_num):\n",
    "                        res = max(res,cum_sum-sorted_num[idx])\n",
    "                    bisect.insort(sorted_num,cum_sum)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = float('-inf')\n",
    "\n",
    "        for i in range(m):\n",
    "            sums = [0] * n\n",
    "            for j in range(i,m):\n",
    "                for c in range(n):\n",
    "                    sums[c] += matrix[j][c]\n",
    "                \n",
    "                sorted_sums = [0]\n",
    "                cur_sum = 0\n",
    "                for s in sums:\n",
    "                    cur_sum += s\n",
    "                    idx = bisect_left(sorted_sums, cur_sum - k)\n",
    "                    if idx < len(sorted_sums):\n",
    "                        res = max(res, cur_sum - sorted_sums[idx])\n",
    "                    bisect.insort(sorted_sums, cur_sum)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        # 定完边界后用到了二分法函数bisect.bisect_left求插入下标,bisect.insort插入\n",
    "        # 定义\n",
    "        row = len(matrix)     # 行数\n",
    "        col = len(matrix[0])  # 列数\n",
    "        res = float(\"-inf\")   # 结果变量，先定为负无穷\n",
    "        # 遍历：从左到右，从上到下\n",
    "        for left in range(col):  # 固定左边界\n",
    "            colSum = [0] * row   # 这一列（左边界）的每行总和\n",
    "            for right in range(left, col):   # 固定右边界,colSum在遍历的每一列都会叠加\n",
    "                for i in range(row):         # 从上到下\n",
    "                    colSum[i] += matrix[i][right]   # 每一行同位置叠加\n",
    "                \n",
    "                res_list = [0]  # 各矩阵的累计和\n",
    "                cur = 0\n",
    "                for num in colSum:\n",
    "                    cur += num\n",
    "                    # # 二分left查找cur-k，如位置在res_list中，说明当前累计和cur减去k小于等于res_list中的某个已经存在的累计和\n",
    "                    loc = bisect.bisect_left(res_list, cur - k)  \n",
    "                    if loc < len(res_list):\n",
    "                        new_res = cur - res_list[loc]\n",
    "                        if new_res == k:\n",
    "                            return k\n",
    "                        else:\n",
    "                            res = max(new_res, res)\n",
    "                    # 把当前累计和cur加入res_list，继续计算，比较\n",
    "                    bisect.insort(res_list, cur)\n",
    "        return res            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        row , col = len(matrix) , len(matrix[0])\n",
    "        res = float(\"-inf\")\n",
    "        for left in range(col):\n",
    "            sums = [0] * row\n",
    "            for right in range(left,col):\n",
    "                for j in range(row):\n",
    "                    sums[j] += matrix[j][right]\n",
    "                lst = [0]\n",
    "                cur = 0\n",
    "                for num in sums:\n",
    "                    cur += num\n",
    "                    loc = bisect.bisect_left(lst,cur-k)\n",
    "                    if loc < len(lst):\n",
    "                        res = max(cur-lst[loc],res)\n",
    "                    bisect.insort(lst,cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "    #     # 1.Brute force solution, this will exceed the momory limit\n",
    "    #     # time complexity: (M^2*N^2)\n",
    "    #     # space complexity: (M^2*N^2)\n",
    "    #     m, n = len(matrix) + 1, len(matrix[0]) + 1\n",
    "    #     dp = [\n",
    "    #         [[[0 for _ in range(n)] for _ in range(m)] for _ in range(n)]\n",
    "    #         for _ in range(m)\n",
    "    #     ]\n",
    "\n",
    "    #     max_val = -float(\"inf\")\n",
    "\n",
    "    #     for i1 in range(1, m):\n",
    "    #         for j1 in range(1, n):\n",
    "    #             dp[i1][j1][i1][j1] = matrix[i1 - 1][j1 - 1]\n",
    "    #             for i2 in range(i1, m):\n",
    "    #                 for j2 in range(j1, n):\n",
    "    #                     dp[i1][j1][i2][j2] = (\n",
    "    #                         dp[i1][j1][i2][j2 - 1]\n",
    "    #                         + dp[i1][j1][i2 - 1][j2]\n",
    "    #                         - dp[i1][j1][i2 - 1][j2 - 1]\n",
    "    #                         + matrix[i2 - 1][j2 - 1]\n",
    "    #                     )\n",
    "\n",
    "    #                     if dp[i1][j1][i2][j2] <= k:\n",
    "    #                         max_val = max(max_val, dp[i1][j1][i2][j2])\n",
    "    #     return max_val\n",
    "\n",
    "    # def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "    #     # 2.Brute force solution with space optimization, this will exceed the time limit\n",
    "    #     # time complexity: (M^2*N^2)\n",
    "    #     # space complexity: (M*N)\n",
    "    #     m, n = len(matrix) + 1, len(matrix[0]) + 1\n",
    "    #     max_val = -float(\"inf\")\n",
    "\n",
    "    #     for i1 in range(1, m):\n",
    "    #         for j1 in range(1, n):\n",
    "    #             dp = [[0 for _ in range(n)] for _ in range(m)]\n",
    "    #             dp[i1][j1] = matrix[i1 - 1][j1 - 1]\n",
    "\n",
    "    #             for i2 in range(i1, m):\n",
    "    #                 for j2 in range(j1, n):\n",
    "    #                     dp[i2][j2] = (\n",
    "    #                         dp[i2 - 1][j2]\n",
    "    #                         + dp[i2][j2 - 1]\n",
    "    #                         - dp[i2 - 1][j2 - 1]\n",
    "    #                         + matrix[i2 - 1][j2 - 1]\n",
    "    #                     )\n",
    "\n",
    "    #                     if dp[i2][j2] <= k:\n",
    "    #                         max_val = max(max_val, dp[i2][j2])\n",
    "    #     return max_val\n",
    "\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        # 3.Brute force solution with space optimization, this will exceed the time limit\n",
    "        # time complexity: (M^2*N^2)\n",
    "        # space complexity: (M*N)\n",
    "\n",
    "        \"\"\"\n",
    "        If we enumerate the upper and lower boundaries of the rectangle and calculate the sum of elements in each column within the boundary, the original problem is transformed into the following one-dimensional problem:\n",
    "        Given an array of integers and an integer k, calculate the maximum interval sum of the array, requiring that the interval sum does not exceed k.\n",
    "        \"\"\"\n",
    "\n",
    "        def maximum_subarray_below_k(nums: List[int], k: int) -> int:\n",
    "            n = len(nums) + 1\n",
    "\n",
    "            roll_sum = roll_max = nums[0]\n",
    "            for i in range(1, n - 1):\n",
    "                if roll_sum > 0:\n",
    "                    roll_sum += nums[i]\n",
    "                else:\n",
    "                    roll_sum = nums[i]\n",
    "\n",
    "                roll_max = max(roll_max, roll_sum)\n",
    "\n",
    "            if roll_max <= k:\n",
    "                return roll_max\n",
    "\n",
    "            max_val = float(\"-inf\")\n",
    "\n",
    "            for i in range(1, n):\n",
    "                total = 0\n",
    "                for j in range(i, n):\n",
    "                    total += nums[j - 1]\n",
    "                    if total > max_val and total <= k:\n",
    "                        max_val = total\n",
    "                    if total == k:\n",
    "                        return total\n",
    "\n",
    "            return max_val\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        max_val = -float(\"inf\")\n",
    "\n",
    "        # Enumerate the upper boundary\n",
    "        for i_upper in range(m):\n",
    "            row_sums = [0 for _ in range(n)]\n",
    "            # Enumerate the lower boundary\n",
    "            for i_lower in range(i_upper, m):\n",
    "                for c in range(n):\n",
    "                    row_sums[c] += matrix[i_lower][c]\n",
    "                max_val = max(max_val, maximum_subarray_below_k(row_sums, k))\n",
    "        return max_val\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0])\n",
    "        max_area = float('-inf')\n",
    "\n",
    "        for left in range(cols):\n",
    "            temp = [0] * rows\n",
    "            for right in range(left, cols):\n",
    "                for i in range(rows):\n",
    "                    temp[i] += matrix[i][right]\n",
    "\n",
    "                # Apply Kadane's algorithm to find the maximum subarray sum not exceeding k\n",
    "                prefix_sums = [0]\n",
    "                curr_sum = 0\n",
    "\n",
    "                for i in range(rows):\n",
    "                    curr_sum += temp[i]\n",
    "                    # Find the smallest prefix sum such that curr_sum - prefix_sum <= k\n",
    "                    target = curr_sum - k\n",
    "                    insert_pos = bisect_left(prefix_sums, target)\n",
    "                    if insert_pos < len(prefix_sums):\n",
    "                        max_sum = curr_sum - prefix_sums[insert_pos]\n",
    "                        if max_sum == k:\n",
    "                            return k  # Found an area equal to k, no need to continue\n",
    "                        if max_sum > max_area:\n",
    "                            max_area = max_sum\n",
    "\n",
    "                    # Insert curr_sum into prefix_sums while maintaining sorted order\n",
    "                    insort_left(prefix_sums, curr_sum)\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float('-inf')\n",
    "        column = len(matrix[0])\n",
    "        rows = len(matrix)\n",
    "\n",
    "        for left in range(column):\n",
    "            nums = [0] * rows\n",
    "            for right in range(left, column):\n",
    "                for i in range(rows):\n",
    "                    nums[i] += matrix[i][right]\n",
    "                array = [0]\n",
    "                now = 0\n",
    "                for n in nums:\n",
    "                    now += n\n",
    "                    idx = bisect.bisect_left(array, now - k)\n",
    "                    if idx < len(array):\n",
    "                        ans = max(ans, now - array[idx])\n",
    "                    bisect.insort(array, now)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findMax(self, row_result, max_tmp, target):\n",
    "        length = len(row_result)\n",
    "        for i in range(length):\n",
    "            sum_ = 0\n",
    "            for j in range(i, length):\n",
    "                sum_ += row_result[j]\n",
    "                if sum_ <= target and sum_ > max_tmp:\n",
    "                    if sum_ ==  target:\n",
    "                        return sum_\n",
    "                    else:max_tmp = sum_\n",
    "        return max_tmp\n",
    "\n",
    "\n",
    "\n",
    "    def maxSumSubmatrix(self, matrix, k):\n",
    "        rows = len(matrix)\n",
    "        if rows == 0:\n",
    "            return 0\n",
    "        cols = len(matrix[0])\n",
    "        max_ = float(\"-inf\")\n",
    "        for c in range(cols):\n",
    "            tmp = [0] * rows\n",
    "            for c1 in range(c, cols):\n",
    "                for r in range(rows):\n",
    "                    tmp[r] += matrix[r][c1]\n",
    "\n",
    "                max_ = self.findMax(tmp, max_, k)\n",
    "        return max_\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        res = -int(1e9)\n",
    "        for i in range(m):\n",
    "            nums = [0] * n\n",
    "            for j in range(i, m):\n",
    "                tmp = [0]\n",
    "                s = 0\n",
    "                for c in range(n):\n",
    "                    nums[c] += matrix[j][c]\n",
    "                    s += nums[c]\n",
    "                    t = s - k\n",
    "                    idx = bisect.bisect_left(tmp, t)\n",
    "                    if idx < len(tmp):\n",
    "                        res = max(res, s - tmp[idx])\n",
    "                        if res == k:\n",
    "                            return res\n",
    "                    bisect.insort(tmp, s)\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = [0]\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                        if ans == k:\n",
    "                            return ans\n",
    "                    if t not in sl:\n",
    "                        bisect.insort(sl, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = [0]\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                        if ans == k:\n",
    "                            return ans\n",
    "                    bisect.insort(sl, t) # 似乎比SortedList快\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for j in range(n):\n",
    "            for i in range(1, m):\n",
    "                matrix[i][j] += matrix[i-1][j]\n",
    "\n",
    "        ans = float('-inf')\n",
    "        for i in range(m):\n",
    "            for j in range(i, m):\n",
    "                pre = 0\n",
    "                pre_list = [0]\n",
    "                for c in range(n):\n",
    "                    pre += matrix[j][c] - (matrix[i-1][c] if i > 0 else 0)\n",
    "                    idx = bisect.bisect_left(pre_list, pre - k)\n",
    "                    if idx < len(pre_list):\n",
    "                        ans = max(ans, pre - pre_list[idx])\n",
    "                    bisect.insort(pre_list, pre)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m,n= len(matrix),len(matrix[0])\n",
    "        res = -inf\n",
    "        for x in range(m):\n",
    "            prefix = [0]*n\n",
    "            for i in range(x,m):\n",
    "                dp = [0]\n",
    "                for j in range(n):\n",
    "                    prefix[j]+=matrix[i][j]\n",
    "                pre = 0\n",
    "                for p in prefix:\n",
    "                    pre+=p\n",
    "                    idx = bisect.bisect_left(dp,pre-k)\n",
    "                    if idx<len(dp):\n",
    "                        res = max(res,pre-dp[idx])\n",
    "                    bisect.insort(dp,pre)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        rows = len(matrix)\n",
    "        cols = len(matrix[0])\n",
    "        max_area = float('-inf')\n",
    "\n",
    "        for left in range(cols):\n",
    "            temp = [0] * rows\n",
    "            for right in range(left, cols):\n",
    "                for i in range(rows):\n",
    "                    temp[i] += matrix[i][right]\n",
    "\n",
    "                # Apply Kadane's algorithm to find the maximum subarray sum not exceeding k\n",
    "                prefix_sums = [0]\n",
    "                curr_sum = 0\n",
    "\n",
    "                for i in range(rows):\n",
    "                    curr_sum += temp[i]\n",
    "                    # Find the smallest prefix sum such that curr_sum - prefix_sums <= k\n",
    "                    target = curr_sum - k\n",
    "                    insert_pos = bisect_left(prefix_sums, target)\n",
    "                    if insert_pos < len(prefix_sums):\n",
    "                        max_sum = curr_sum - prefix_sums[insert_pos]\n",
    "                        if max_sum == k:\n",
    "                            return k  # Found an area equal to k, no need to continue\n",
    "                        if max_sum > max_area:\n",
    "                            max_area = max_sum\n",
    "\n",
    "                    # Insert curr_sum into prefix_sums while maintaining sorted order\n",
    "                    insort_left(prefix_sums, curr_sum)\n",
    "\n",
    "        return max_area"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -math.inf\n",
    "        for i in range(m):\n",
    "            col_sum = [0] * n\n",
    "            for j in range(i, m):\n",
    "                sl = SortedList()\n",
    "                sl.add(0)\n",
    "                area_sum = 0\n",
    "                for l in range(n):\n",
    "                    col_sum[l] += matrix[j][l] \n",
    "                    area_sum += col_sum[l] \n",
    "                    idx = sl.bisect_left(area_sum - k) \n",
    "                    if idx < len(sl):\n",
    "                        ans = max(ans, area_sum - sl[idx]) \n",
    "                    sl.add(area_sum)\n",
    "        return ans \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        preSum = [[0 for _ in range(n+1)] for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(1, n+1):\n",
    "                preSum[i][j] = preSum[i][j-1] + matrix[i][j-1]\n",
    "                \n",
    "        res = float('-inf')\n",
    "        for colA in range(1, n+1):\n",
    "            for colB in range(colA, n+1):\n",
    "                slist, cur = [0], 0\n",
    "                for row in range(m):\n",
    "                    cur += preSum[row][colB] - preSum[row][colA-1]\n",
    "                    # idx = self.bsearch(slist, cur-k)\n",
    "                    idx = bisect.bisect_left(slist, cur-k)\n",
    "                    if idx < len(slist):\n",
    "                        res = max(res, cur-slist[idx])\n",
    "                    # insert_idx = self.bsearch(slist, cur)\n",
    "                    # slist.insert(insert_idx, cur)\n",
    "                    bisect.insort(slist, cur)\n",
    "        return res\n",
    "                    \n",
    "    \n",
    "    def bsearch(self, nums, target):\n",
    "        l, r = 0, len(nums) - 1\n",
    "        while l <= r:\n",
    "            mid = (l + r) >> 1\n",
    "            if nums[mid] >= target:\n",
    "                r = mid - 1\n",
    "            else:\n",
    "                l = mid + 1\n",
    "        return l\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = [0]\n",
    "                vset = set()\n",
    "                vset.add(0)\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                        if ans == k:\n",
    "                            return ans\n",
    "                    if t not in vset:\n",
    "                        bisect.insort(sl, t)\n",
    "                        vset.add(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], tk: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        max_s = -inf\n",
    "        for i in range(m):\n",
    "            b = [0 for _ in range(n)]\n",
    "            for j in range(i, m):\n",
    "                s = 0\n",
    "                for k in range(n):\n",
    "                    b[k] += matrix[j][k]\n",
    "                for p in range(n):\n",
    "                    s = 0\n",
    "                    for q in range(p, n):\n",
    "                        s += b[q]\n",
    "                        if s > max_s and s <= tk:\n",
    "                            max_s = s\n",
    "        return max_s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = [0]\n",
    "                vset = set()\n",
    "                vset.add(0)\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                        if ans == k:\n",
    "                            return ans\n",
    "                    if t not in vset:\n",
    "                        bisect.insort(sl, t)\n",
    "                        vset.add(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        n,m=len(matrix),len(matrix[0])\n",
    "        ans = float(\"-inf\")\n",
    "        for i in range(n):\n",
    "            total=[0]*m\n",
    "            for j in range(i,n):\n",
    "                for c in range(m):\n",
    "                    total[c]+=matrix[j][c]\n",
    "                \n",
    "                totalSet=SortedList([0])\n",
    "                s=0\n",
    "                for v in total:\n",
    "                    s+=v\n",
    "                    lb=totalSet.bisect_left(s-k)\n",
    "                    if lb!=len(totalSet):\n",
    "                        ans=max(ans,s-totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = [0]\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                        if ans == k:\n",
    "                            return ans\n",
    "                    bisect.insort(sl, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        preSum = [[0 for _ in range(n+1)] for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(1, n+1):\n",
    "                preSum[i][j] = preSum[i][j-1] + matrix[i][j-1]\n",
    "                \n",
    "        res = float('-inf')\n",
    "        for colA in range(1, n+1):\n",
    "            for colB in range(colA, n+1):\n",
    "                slist, cur = [0], 0\n",
    "                for row in range(m):\n",
    "                    cur += preSum[row][colB] - preSum[row][colA-1]\n",
    "                    # idx = self.bsearch(slist, cur-k)\n",
    "                    idx = bisect.bisect_left(slist, cur-k)\n",
    "                    if idx < len(slist):\n",
    "                        res = max(res, cur-slist[idx])\n",
    "                    # insert_idx = self.bsearch(slist, cur)\n",
    "                    # slist.insert(insert_idx, cur)\n",
    "                    bisect.insort(slist, cur)\n",
    "        return res\n",
    "                    \n",
    "    \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = [0]\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                        if ans == k:\n",
    "                            return ans\n",
    "                    if t not in sl:\n",
    "                        bisect.insort(sl, t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import bisect\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        preSum = [[0 for _ in range(n+1)] for _ in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(1, n+1):\n",
    "                preSum[i][j] = preSum[i][j-1] + matrix[i][j-1]\n",
    "                \n",
    "        res = float('-inf')\n",
    "        for colA in range(1, n+1):\n",
    "            for colB in range(colA, n+1):\n",
    "                slist, cur = [0], 0\n",
    "                for row in range(m):\n",
    "                    cur += preSum[row][colB] - preSum[row][colA-1]\n",
    "                    # idx = self.bsearch(slist, cur-k)\n",
    "                    idx = bisect.bisect_left(slist, cur-k)\n",
    "                    if idx < len(slist):\n",
    "                        res = max(res, cur-slist[idx])\n",
    "                    # insert_idx = self.bsearch(slist, cur)\n",
    "                    # slist.insert(insert_idx, cur)\n",
    "                    bisect.insort(slist, cur)\n",
    "        return res\n",
    "                    \n",
    "    \n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], target: int) -> int:\n",
    "        m,n = len(matrix), len(matrix[0])\n",
    "        ans = -inf\n",
    "        for i in range(m):\n",
    "            t = [0]*n\n",
    "            for j in range(i,m):\n",
    "                \n",
    "                for k in range(n):\n",
    "                    t[k]+=matrix[j][k]\n",
    "                s = SortedList([0])\n",
    "                cur = 0\n",
    "                for v in t:\n",
    "                    cur += v\n",
    "                    pos = bisect_left(s, cur - target)\n",
    "                    if pos!=len(s):\n",
    "                        ans = max(ans, cur-s[pos])\n",
    "                    s.add(cur)\n",
    " \n",
    "\n",
    "            \n",
    "\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        # the some is no larger than k\n",
    "        # same as the max sub matrix\n",
    "        # compress to 1d arr, and only num needed\n",
    "        # O(n)\n",
    "        def findmaxsubwithK(nums, k):\n",
    "            if not nums:\n",
    "                return 0\n",
    "\n",
    "            max_sum = float('-inf')\n",
    "            current_sum = 0\n",
    "            prefix_sums = [0]\n",
    "\n",
    "            for num in nums:\n",
    "                current_sum += num\n",
    "                index = bisect.bisect_left(prefix_sums, current_sum - k)\n",
    "                if index < len(prefix_sums):\n",
    "                    max_sum = max(max_sum, current_sum - prefix_sums[index])\n",
    "                bisect.insort(prefix_sums, current_sum)\n",
    "\n",
    "            return max_sum\n",
    "\n",
    "        # compress between i0 and i1\n",
    "        n, m = len(matrix), len(matrix[0])\n",
    "        precolsum = [[-inf]*m for _ in range(n)]\n",
    "        precolsum[0] = matrix[0]\n",
    "        for i in range(1, n):\n",
    "            for j in range(m):\n",
    "                precolsum[i][j] = precolsum[i-1][j] + matrix[i][j]\n",
    "        # print(precolsum)\n",
    "\n",
    "        maxval = -inf\n",
    "        # start\n",
    "        for i0 in range(n):\n",
    "            for i1 in range(i0, n):\n",
    "                if i0 - 1 >= 0:\n",
    "                    tmp_arr = [precolsum[i1][j] - precolsum[i0-1][j] for j in range(m)]\n",
    "                else:\n",
    "                    tmp_arr = precolsum[i1][:]\n",
    "\n",
    "                tmpval = findmaxsubwithK(tmp_arr, k)\n",
    "                maxval = max(maxval, tmpval)\n",
    "                \n",
    "        return maxval\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], K: int) -> int:\n",
    "        ans = float('-inf')\n",
    "\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                \n",
    "                totalList = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    idx =  totalList.bisect_left(s - K)\n",
    "                    if idx != len(totalList):\n",
    "                        ans = max(ans, s - totalList[idx])\n",
    "                    totalList.add(s)\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):   # 枚举上边界\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):   # 枚举下边界\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]   # 更新每列的元素和\n",
    "                \n",
    "                totalSet = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    lb = totalSet.bisect_left(s - k)\n",
    "                    if lb != len(totalSet):\n",
    "                        ans = max(ans, s - totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):   # 枚举上边界\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):   # 枚举下边界\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]   # 更新每列的元素和\n",
    "                \n",
    "                totalSet = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    lb = totalSet.bisect_left(s - k)\n",
    "                    if lb != len(totalSet):\n",
    "                        ans = max(ans, s - totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], K: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(1, n):\n",
    "                matrix[i][j] += matrix[i][j - 1]\n",
    "        ans = float(\"-inf\")\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                pres = SortedList([0])\n",
    "                pre = 0\n",
    "                for k in range(m):\n",
    "                    pre += matrix[k][j] - (0 if i == 0 else matrix[k][i - 1])\n",
    "                    # 寻找小于等于 pre - k 的最大数。\n",
    "                    # 为了达到这个目的，可以使用 bisect_left 来完成。（使用 bisect_right 不包含等号）\n",
    "                    idx = pres.bisect_left(pre - K)\n",
    "                    # 如果 i == len(pre) 表示无解\n",
    "                    if idx < len(pres):\n",
    "                        ans = max(ans, pre - pres[idx])\n",
    "                    pres.add(pre)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "\n",
    "        for i in range(m): #枚举上边界\n",
    "            total = [0]*n\n",
    "            for j in range(i,m): #枚举下边界\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c] # 更新每列的元素和\n",
    "                \n",
    "                totalSet = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s+=v\n",
    "                    lb = totalSet.bisect_left(s-k)\n",
    "                    if lb != len(totalSet):\n",
    "                        ans = max(ans,s-totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans=float('-inf')\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        for i in range(m):\n",
    "            total=[0]*n\n",
    "            for j in range(i,m):\n",
    "                for c in range(n):\n",
    "                    total[c]+=matrix[j][c]\n",
    "                totalset=SortedList([0])\n",
    "                s=0\n",
    "                for v in total:\n",
    "                    s+=v\n",
    "                    lb=totalset.bisect_left(s-k)\n",
    "                    if lb!=len(totalset):\n",
    "                        ans=max(ans,s-totalset[lb])\n",
    "                    totalset.add(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        maxsum = -inf\n",
    "        for i in range(m):\n",
    "            dp = [0]*n\n",
    "            for j in range(i,m):\n",
    "                for l in range(n):\n",
    "                    dp[l]+=matrix[j][l]\n",
    "            \n",
    "                totalset = SortedList([0])\n",
    "                s = 0\n",
    "                for v in dp:\n",
    "                    s+=v\n",
    "                    index = totalset.bisect_left(s-k)\n",
    "                    if index != len(totalset):\n",
    "                        maxsum = max(maxsum,s-totalset[index])\n",
    "                    totalset.add(s)\n",
    "        return maxsum\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):   # 枚举上边界\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):   # 枚举下边界\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]   # 更新每列的元素和\n",
    "                \n",
    "                totalSet = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    lb = totalSet.bisect_left(s - k)\n",
    "                    if lb != len(totalSet):\n",
    "                        ans = max(ans, s - totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float('-inf')\n",
    "        m,n = len(matrix),len(matrix[0])\n",
    "\n",
    "        for i in range(m):\n",
    "            col_sum = [0]*(n)\n",
    "            for j in range(i,m):\n",
    "                for c in range(n):\n",
    "                    col_sum[c]+=matrix[j][c]\n",
    "                \n",
    "                total_set = SortedList([0])\n",
    "                s= 0 \n",
    "                for the_sum in col_sum:\n",
    "                    s+=the_sum\n",
    "                    idx = total_set.bisect_left(s-k)\n",
    "                    if idx!=len(total_set):\n",
    "                        ans = max(ans, s-total_set[idx])\n",
    "                    total_set.add(s)\n",
    "        \n",
    "        return ans\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "import bisect\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ret = -1e6\n",
    "        for u in range(m):\n",
    "            tot = [0] * n\n",
    "            for d in range(u, m):\n",
    "                for j in range(n):\n",
    "                    tot[j] += matrix[d][j]\n",
    "\n",
    "                l = SortedList([0])\n",
    "                s = 0\n",
    "                for i in range(n):\n",
    "                    s += tot[i]\n",
    "                    target = s - k\n",
    "                    r = l.bisect_left(target)\n",
    "                    if r != len(l):\n",
    "                        ret = max(ret, s - l[r])\n",
    "                    l.add(s)\n",
    "        return ret\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = SortedList([0])\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                    sl.add(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m = len(matrix)\n",
    "        n = len(matrix[0])\n",
    "        for i in range(m):\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]\n",
    "                total_set = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    lb = total_set.bisect_left(s - k)\n",
    "                    if lb != len(total_set):\n",
    "                        ans = max(ans, s - total_set[lb])\n",
    "                    total_set.add(s)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):   # 枚举上边界\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):   # 枚举下边界\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]   # 更新每列的元素和\n",
    "                \n",
    "                totalSet = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    lb = totalSet.bisect_left(s - k)\n",
    "                    if lb != len(totalSet):\n",
    "                        ans = max(ans, s - totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], target_k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = -inf\n",
    "        for i in range(m):\n",
    "            b = [0 for _ in range(n)]\n",
    "            for j in range(i, m):\n",
    "                for k in range(n):\n",
    "                    b[k] += matrix[j][k]\n",
    "\n",
    "                s = 0\n",
    "                s_set = SortedList([s])\n",
    "                for x in b:\n",
    "                    s += x\n",
    "                    lb = bisect_left(s_set, s - target_k)\n",
    "                    if lb < len(s_set):\n",
    "                        res = max(res, s - s_set[lb])\n",
    "                    s_set.add(s)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], target_k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        res = -inf\n",
    "        for i in range(m):\n",
    "            b = [0 for _ in range(n)]\n",
    "            for j in range(i, m):\n",
    "                for k in range(n):\n",
    "                    b[k] += matrix[j][k]\n",
    "\n",
    "                s = 0\n",
    "                s_set = SortedList([s])\n",
    "                for x in b:\n",
    "                    s += x\n",
    "                    lb = bisect_left(s_set, s - target_k)\n",
    "                    if lb < len(s_set):\n",
    "                        res = max(res, s - s_set[lb])\n",
    "                        if res == target_k:\n",
    "                            return res\n",
    "                    s_set.add(s)\n",
    "        \n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ''' 暴力超时\n",
    "        # 求和\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for c in range(1, n):\n",
    "            matrix[0][c] += matrix[0][c - 1]\n",
    "        for r in range(1, m):\n",
    "            matrix[r][0] += matrix[r - 1][0]\n",
    "            for c in range(1, n):\n",
    "                matrix[r][c] += matrix[r][c - 1] + matrix[r - 1][c] - matrix[r - 1][c - 1]\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            for c0 in range(n):\n",
    "                s0 = 0\n",
    "                if r0 > 0 and c0 > 0:\n",
    "                    s0 = matrix[r0 - 1][c0 - 1]\n",
    "                for r in range(r0, m):\n",
    "                    for c in range(c0, n):\n",
    "                        s = matrix[r][c] + s0\n",
    "                        if r0 > 0:\n",
    "                            s -= matrix[r0 - 1][c]\n",
    "                        if c0 > 0:\n",
    "                            s -= matrix[r][c0 - 1]\n",
    "                        if s <= k and s > ans:\n",
    "                            ans = s \n",
    "        return ans\n",
    "        '''\n",
    "        # 固定上下边界，转换为求满足条件数组子序列和\n",
    "        # 可以维护一个有序数组(SortedList)，存储当前位置之前的和，然后通过二分法查找满足条件的值\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ans = -100000\n",
    "        for r0 in range(m):\n",
    "            s = [0] * n\n",
    "            for r1 in range(r0, m):\n",
    "                # 更新所有列的和\n",
    "                for c in range(n):\n",
    "                    s[c] += matrix[r1][c]\n",
    "                sl = SortedList([0])\n",
    "                t = 0\n",
    "                for si in s:\n",
    "                    t += si\n",
    "                    i = bisect.bisect_left(sl, t - k)\n",
    "                    if i < len(sl):\n",
    "                        ans = max(ans, t - sl[i])\n",
    "                        if ans == k:\n",
    "                            return ans\n",
    "                    sl.add(t)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans=float('-inf')\n",
    "        m,n=len(matrix),len(matrix[0])\n",
    "        \n",
    "        for i in range(m):\n",
    "            total=[0]*n\n",
    "            for j in range(i,m):\n",
    "                for c in range(n):\n",
    "                    total[c]+=matrix[j][c]\n",
    "                \n",
    "                totalset=SortedList([0])\n",
    "                s=0\n",
    "                for v in total:\n",
    "                    s+=v\n",
    "                    lb=totalset.bisect_left(s-k)\n",
    "                    if lb!=len(totalset):\n",
    "                        ans=max(ans,s-totalset[lb])\n",
    "                    totalset.add(s)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        \n",
    "        # 计算前缀和\n",
    "        pre_sum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pre_sum[i + 1][j + 1] = pre_sum[i + 1][j] + pre_sum[i][j + 1] - pre_sum[i][j] + matrix[i][j]\n",
    "\n",
    "        ans = float('-inf')\n",
    "        # 枚举矩形的上下两边以及右下端点，同时维护一个左下端点前缀和的有序集合\n",
    "        for r1 in range(m):\n",
    "            for r2 in range(r1, m):\n",
    "                pre = SortedList()\n",
    "                # 存储的是pre_sum[r2+1][0~n]-pre_sum[r1][0~n]的值，由于上下两边确定，因此遍历右下端点时搜寻的是减去左下端点的前缀和\n",
    "                pre.add(0)\n",
    "                for j in range(n):\n",
    "                    # 查找当前作为右下端点最接近目标的子矩阵和\n",
    "                    cur = pre_sum[r2 + 1][j + 1] - pre_sum[r1][j + 1]\n",
    "                    c = pre.bisect_left(cur - k)\n",
    "                    if c < len(pre) :\n",
    "                        ans = max(cur - pre[c],ans)\n",
    "                    pre.add(cur)\n",
    "                \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#矩形区域不超过 K 的最大数值和,动态规划\n",
    "#输入：matrix = [[1,0,1],[0,-2,3]], k = 2；输出：2；输入：matrix = [[2,2,-1]], k = 3输出：3\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):   # 枚举上边界\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):   # 枚举下边界\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]   # 更新每列的元素和\n",
    "                \n",
    "                totalSet = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    lb = totalSet.bisect_left(s - k)\n",
    "                    if lb != len(totalSet):\n",
    "                        ans = max(ans, s - totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import sortedcontainers\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix, k):\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        presum = [[0] * (n + 1) for _ in range(m + 1)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                presum[i + 1][j + 1] = presum[i][j + 1] + presum[i + 1][j] + matrix[i][j] - presum[i][j]\n",
    "        \n",
    "        ret = -sys.maxsize\n",
    "        for i in range(n):  # Any two rows\n",
    "            for j in range(i + 1, n + 1):\n",
    "                s = sortedcontainers.SortedSet([0])  # Use a sorted set to store cumulative sums, initialize with 0\n",
    "                \n",
    "                for t in range(1, m + 1):  # Two rows fixed, iterate column by column\n",
    "                    _sum = self.sumRange(0, i, t, j, presum)\n",
    "                    lower = s.bisect_left(_sum - k)  # Find the lower bound using binary search\n",
    "                    if lower != len(s):\n",
    "                        ret = max(ret, _sum - s[lower])  # Update the result if found a valid sum\n",
    "                    s.add(_sum)  # Add the current sum to the sorted set\n",
    "        \n",
    "        return ret\n",
    "    \n",
    "    def sumRange(self, x1, y1, x2, y2, presum):\n",
    "        return presum[x2][y2] - presum[x1][y2] - presum[x2][y1] + presum[x1][y1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        n,m = len(matrix),len(matrix[0])\n",
    "        presum = [[0] * (m + 1) for _ in range(n + 1)]\n",
    "\n",
    "        for i in range(1,n + 1):\n",
    "            for j in range(1,m + 1):\n",
    "                presum[i][j] = presum[i - 1][j] + presum[i][j - 1] - presum[i - 1][j - 1] + matrix[i - 1][j - 1]\n",
    "\n",
    "\n",
    "        ans = -float('inf')\n",
    "\n",
    "        for x1 in range(1,n + 1):\n",
    "            for x2 in range(x1,n + 1):\n",
    "                s = SortedList()\n",
    "\n",
    "                for r in range(1,m + 1):\n",
    "                    cur = presum[x2][r] - presum[x1 - 1][r]\n",
    "                    if cur <= k:\n",
    "                        ans = max(ans,cur)\n",
    "\n",
    "                    idx = s.bisect_left(cur - k)\n",
    "                    if idx < len(s) and cur - k <= s[idx]:\n",
    "                        ans = max(ans,cur - s[idx])\n",
    "                    s.add(cur)\n",
    "\n",
    "            \n",
    "        return ans\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        ans = float(\"-inf\")\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "\n",
    "        for i in range(m):   # 枚举上边界\n",
    "            total = [0] * n\n",
    "            for j in range(i, m):   # 枚举下边界\n",
    "                for c in range(n):\n",
    "                    total[c] += matrix[j][c]   # 更新每列的元素和\n",
    "                \n",
    "                totalSet = SortedList([0])\n",
    "                s = 0\n",
    "                for v in total:\n",
    "                    s += v\n",
    "                    lb = totalSet.bisect_left(s - k)\n",
    "                    if lb != len(totalSet):\n",
    "                        ans = max(ans, s - totalSet[lb])\n",
    "                    totalSet.add(s)\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], K: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(1, n):\n",
    "                matrix[i][j] += matrix[i][j - 1]\n",
    "        ans = float(\"-inf\")\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                pres = SortedList([0])\n",
    "                pre = 0\n",
    "                for k in range(m):\n",
    "                    pre += matrix[k][j] - (0 if i == 0 else matrix[k][i - 1])\n",
    "                    # 寻找小于等于 pre - k 的最大数。\n",
    "                    # 为了达到这个目的，可以使用 bisect_left 来完成。（使用 bisect_right 不包含等号）\n",
    "                    idx = pres.bisect_left(pre - K)\n",
    "                    # 如果 i == len(pre) 表示无解\n",
    "                    if idx < len(pres):\n",
    "                        ans = max(ans, pre - pres[idx])\n",
    "                    pres.add(pre)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        res, R, C = -inf, len(matrix), len(matrix[0])\n",
    "        for i in range(R):\n",
    "            nums = [0] * C\n",
    "            for j in range(i, R):\n",
    "                for c in range(C):\n",
    "                    nums[c] += matrix[j][c]\n",
    "                presum, sortedList = 0, SortedList([0])\n",
    "                for n in nums:\n",
    "                    presum += n\n",
    "                    idx = sortedList.bisect_left(presum - k)\n",
    "                    if idx < len(sortedList):\n",
    "                        res = max(res, presum - sortedList[idx])\n",
    "                    sortedList.add(presum)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], K: int) -> int:\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        for i in range(m):\n",
    "            for j in range(1, n):\n",
    "                matrix[i][j] += matrix[i][j - 1]  #每行都是【横向累加】\n",
    "        ans = float(\"-inf\")\n",
    "        for i in range(n):         #枚举列的起始位置\n",
    "            for j in range(i, n):  #枚举列的结束位置\n",
    "                pres = SortedList([0])\n",
    "                pre = 0\n",
    "                for k in range(m): #枚举行一直累加【纵向累加】\n",
    "                    pre += matrix[k][j] - (0 if i == 0 else matrix[k][i - 1])   # i 到 j 之间的值\n",
    "                    # 寻找小于等于 pre - k 的最大数。（ 先得找到 pre - k 才能找到 k）\n",
    "                    # 为了达到这个目的，可以使用 bisect_left 来完成。（使用 bisect_right 不包含等号）\n",
    "                    idx = pres.bisect_left(pre - K)\n",
    "                    # 如果 i == len(pre) 表示无解\n",
    "                    if idx < len(pres):\n",
    "                        ans = max(ans, pre - pres[idx])\n",
    "                    pres.add(pre)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        pre = list(list(accumulate(m, initial=0)) for m in matrix)\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ret = -inf\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                for x in range(m):\n",
    "                    tmp = 0\n",
    "                    for y in range(x, m):\n",
    "                        tmp += pre[y][j+1] - pre[y][i]\n",
    "                        if tmp <= k :\n",
    "                            ret = max(ret, tmp)\n",
    "        return ret\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], K: int) -> int:\n",
    "        pre = list(list(accumulate(m, initial=0)) for m in matrix)\n",
    "        m, n = len(matrix), len(matrix[0])\n",
    "        ret = -inf\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                pres = SortedList([0])\n",
    "                tmp = 0\n",
    "                for k in range(m):\n",
    "                    tmp += pre[k][j+1] - pre[k][i]\n",
    "                    idx = pres.bisect_left(tmp - K)\n",
    "                    if idx < len(pres):\n",
    "                        ret = max(ret, tmp - pres[idx])\n",
    "                    pres.add(tmp)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:\n",
    "        res, R, C = -inf, len(matrix), len(matrix[0])\n",
    "        for row in matrix:\n",
    "            for c in range(C - 1):\n",
    "                row[c + 1] += row[c]\n",
    "        for i in range(C):\n",
    "            for j in range(i, C):\n",
    "                nums = [matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0) for k in range(R)]\n",
    "                presum, sortedList = 0, SortedList([0])\n",
    "                for n in nums:\n",
    "                    presum += n\n",
    "                    idx = sortedList.bisect_left(presum - k)\n",
    "                    if idx < len(sortedList):\n",
    "                        res = max(res, presum - sortedList[idx])\n",
    "                    sortedList.add(presum)\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
